In many communication systems the data to be transmitted has its own characteristic statistical structure. The most efficient transmission of such data can be accomplished by designing an optimum code that is matched to this statistical structure. The maximum saving in channel capacity can be calculated from the statistical nature of the data by Shannon's Theorem.
Shannon's Theorem treats an information source as sequences of symbols that may be regarded as random samples from a homogeneous population with known and fixed frequency distributions of all orders (i.e., for single symbols, pairs of symbols, triplets of symbols, ... n-tuples of symbols). The term homogeneous implies that any sufficiently long sequence is likely to be typical of the population source and therefore representative of any other source sequence.
Prior-art coding and compression systems have been proposed which use matched codes in a manner suggested by Shannon's Theorem, but these have been disappointing in their performance because they did not take Shannon's idea far enough. In many communication systems the populations often have numerous very long-range dependencies between samples that are difficult to measure adequately, let alone take into account with an optimum code. This applies particularly to information sources obtained by scanning systems in which the image being scanned leads to dependencies between adjacent elements in the scanning direction and orthogonal to it.
Furthermore, in such situations (e.g., for elements of television or facsimile signals), these significant dependencies between samples spaced far apart in the signal obtained by scanning require that a "sufficiently long" sequence for direct application of Shannon's Theorem be impracticably long.
The present invention is directed particularly to code communication for signal sources resulting from scanning systems, but it should be understood that various novel features are herein described which can be used either separately or in combination and with advantage in a variety of bandwidth compression systems. It should also be understood that the term bandwidth compression is used herein to describe, alternatively or in conjunction with, time compression or storage saving systems.
Again, primarily for purposes of illustration, the system to be hereinafter described refers to a facsimile system in which the scanner source is a rotating drum, and in which the signal source consists of binary sequences. However, it is to be understood that suitable modifications would enable systems to be constructed in which a CRT or other type of scanner is used, or in which no scanners at all are used, and that systems could be constructed in which the signal source consisted of sequences of samples having more than two possible values.